package 力扣算法练习.main1.part1;

public class day16 {
    /*
    给你一个非负整数数组nums ，你最初位于数组的第一个位置。
    数组中的每个元素代表你在该位置可以跳跃的最大长度。
    你的目标是使用最少的跳跃次数到达数组的最后一个位置。
    假设你总是可以到达数组的最后一个位置。
    https://leetcode.cn/problems/jump-game-ii
     */
    //错误代码
   /* public int jump(int[] nums) {
        if (nums.length==0||nums.length==1)return 0;
        int temp=nums[0],index=nums.length,count=1;//temp记录可跳跃的格数,index记录长度,count记录换了几次跳跃数
        for (int i = 0;; ) {
            i++;
            temp--;
            if(i==index-1)break;
            if(temp<nums[i]&&temp+i<index-1&&temp+i<nums[i]+i){
                temp=nums[i];
                count++;
            }
        }
        return count;
    }*/
    //官方解
    public int jump(int[] nums) {
        int length = nums.length;
        int end = 0;
        int maxPosition = 0;
        int steps = 0;
        for (int i = 0; i < length - 1; i++) {
            maxPosition = Math.max(maxPosition, i + nums[i]);
            if (i == end) {
                end = maxPosition;
                steps++;
            }
        }
        return steps;
    }
}
